package lib

import (
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         116,
		Discription: "将完全二叉树的每个节点指向右侧节点",
		Level:       2,
		Labels: map[string]int{
			"二叉树": 1,
		},
	})
}

//思路：类似层序遍历，利用上一层的next构建当前层的next
// 对应每一个上一层的节点，做两件事：左孩子指向右孩子，右孩子指向上一层节点的next（假如不为nil）的左孩子
func ConnectNext(root *ds.Node) *ds.Node {
	upper := root
    //遍历到叶子节点的时候就可以退出了
	for upper != nil && upper.Left != nil {
        //记录下一层的第一个节点
		nextUpper := upper.Left
		for upper != nil {
            //同一个父亲的节点相连
			upper.Left.Next = upper.Right
			if upper.Next != nil {
                //不同父亲的节点相连
				upper.Right.Next = upper.Next.Left
			}
			upper = upper.Next
		}

		upper = nextUpper
	}

	return root
}
